Due to the way Windows is structured internally, you can't actually delete IE... Or, at least, not entirely. It's kinda integrated into the operating system. =P
Dunno about Paint, though. I guess just do a Google search for another copy of paint.exe. Shortcut != program, remember, so you might just be having a brainfart in that regard.